Digital halftoning is a branch of computer graphics whose origins date back to 1931. The history of digital halftoning is summarized in "Evolution of Halftoning Technology in the United States Patent Literature," Peter R. Jones, Journal of Electronic Imaging, Vol. 3, No. 3, 1994, pgs. 257-275.
In one form of halftoning, a continuous tone reference image is transformed into a binary image suitable for printing with black ink on white paper. This is accomplished by transformation of image intensities to areas containing black and white patterns. This process was first implemented by exposing a photograph through a piece of glass on which two sets of closely spaced parallel lines at ninety degrees to one another were etched. Dark areas of the photograph became large dots and light areas small dots when exposed through the screen.
Stroke substitution is a form of halftoning in which image intensities are replaced with strokes rather than with patterns of dots. Stroke substitution of a reference image was first introduced in 1987 in the ImagePaint product by ImageWare Research, from which the term "painterly effects" was coined. Paul Haeberli formalized and expanded on this concept in his paper, "Paint by Numbers: Abstract Image Representations," Proceedings SIGGRAPH '90, Computer Graphics Annual Conference Series, 1990, pgs. 207-214. Since that time stroke substitution has surfaced in many commercial paint and video effects systems. Stroke substitution involves replacing areas of a scanned image with areas that resemble strokes of paint, using colors derived from the reference image. Recently, the University of Washington has implemented digital pen and ink systems which use stroke substitution. "Scale-Dependent Reproduction of Pen-and-Ink Illustrations," Mike Salisbury et. al, Proceedings SIGGRAPH '96, Computer Graphics Annual Conference Series, 1996, pgs. 461-468; "Rendering Parametric Surfaces in Pen and Ink," Georges Winkenbach and David H. Salesin, Proceedings SIGGRAPH '96, Computer Graphics Annual Conference Series, 1996, pgs. 469-477; "Interactive Pen-and-Ink Illustration," Michael Salisbury et al., Proceedings SIGGRAPH '94, Computer Graphics Annual Conference Series, 1994, pgs. 101-108.
Prioritized textures were introduced in G. Winkenbach, D. H. Salesin, "Computer-Generated Pen-and-Ink Illustration," Proceedings SIGGRAPH '94, Computer Graphics Annual Conference Series, 1994, pgs. 91-100. A prioritized texture is a collection of strokes, each of which has a drawing priority. Prioritized textures are particularly useful for producing a range of tonal values resembling those present in pen and ink drawings. Light tones are represented by the strokes of the highest priority only. Darker tones are achieved by adding more strokes of lower priority. The darkest tones result when strokes of all priorities are present.